package tree;

/**
 * 1373. 二叉搜索子树的最大键值和
 * 给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
 *
 * 提示：
 * 每棵树有 1 到 40000 个节点。
 * 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。
 */

public class MaxSumBST_1373 {
    int maxSum = 0;
    public int maxSumBST(TreeNode root) {
        int[] res = helper(root);
        return maxSum;
    }

    /**
     * res[0] 记录以 root 为根的二叉树是否是 BST，若为 1 则说明是 BST，若为 0 则说明不是 BST；
     * res[1] 记录以 root 为根的二叉树所有节点中的最小值；
     * res[2] 记录以 root 为根的二叉树所有节点中的最大值；
     * res[3] 记录以 root 为根的二叉树所有节点值之和。
     *
     * @param root
     * @return
     */
    public int[] helper(TreeNode root) {
        // base case
        if (root == null) {
            return new int[]{1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        }

        // 应该是自底向上计算，后序遍历
        int[] left = helper(root.left);
        int[] right = helper(root.right);

        int[] res = new int[4];
        // 判断当前当前节点是不是二叉树
        if (left[0] == 1 && right[0] == 1 && root.val > left[2] && root.val < right[1]) {
            res[0] = 1;
            res[1] = Math.min(root.val, left[1]);
            res[2] = Math.max(root.val, right[2]);
            res[3] = root.val + left[3] + right[3];
            maxSum = Math.max(maxSum, res[3]);
        } else {
            // 如果不是BST，只需要将第0位置为0
            res[0] = 0;
        }

        return res;
    }
}
